package com.ztom.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * 删除并获得点数
 * <p>
 * https://leetcode-cn.com/problems/delete-and-earn/
 *
 * @author ZhangTao
 */
public class Code07DeleteAndEarn {

    public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 将数组中相同的数累加, 转换成了打家劫舍问题
        // 因为相同点数可以一直偷
        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        // 计数法, 因为相邻的要保留
        int[] sum = new int[max + 1];
        for (int num : nums) {
            sum[num] += num;
        }
        return rob(sum);
    }

    private int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int prepre = nums[0];
        int pre = Math.max(nums[0], nums[1]);
        int res = pre;
        for (int i = 2; i < n; i++) {
            res = Math.max(pre, prepre + nums[i]);
            prepre = pre;
            pre = res;
        }
        return res;
    }
}
